//给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。 
//
// 
// 
//
// 
//
// 示例 1： 
// 
// 
//输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
//输出：[[1,0,1],[0,0,0],[1,0,1]]
// 
//
// 示例 2： 
// 
// 
//输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
//输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]
// 
//
// 
//
// 提示： 
//
// 
// m == matrix.length 
// n == matrix[0].length 
// 1 <= m, n <= 200 
// -2³¹ <= matrix[i][j] <= 2³¹ - 1 
// 
//
// 
//
// 进阶： 
//
// 
// 一个直观的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。 
// 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。 
// 你能想出一个仅使用常量空间的解决方案吗？ 
// 
//
// Related Topics 数组 哈希表 矩阵 👍 907 👎 0


package LeetCode.editor.cn;

import java.util.Arrays;

/**
 * @author ldltd
 * @date 2023-08-09 02:16:18
 * @description 73.矩阵置零
 */
public class SetMatrixZeroes{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new SetMatrixZeroes().new Solution();
		  int [][] m={{1,1,1},{1,0,1},{1,1,1}};
		solution.setZeroes(m);
		 System.out.println(Arrays.deepToString(m));
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
//		 时间复杂度：O(mn)，其中 mmm 是矩阵的行数，nnn 是矩阵的列数。我们至多只需要遍历该矩阵两次。
//
//空间复杂度：O(m+n)，其中 mmm 是矩阵的行数，nnn 是矩阵的列数。我们需要分别记录每一行或每一列是否有零出现

    public void setZeroes(int[][] matrix) {
		int m=matrix.length;
		int n=matrix[0].length;
		int []r=new int[m],c=new int[n];
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if(matrix[i][j]==0){
					c[j]=r[i]=-1;
				}
			}
		}
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if(c[j]==-1||r[i]==-1){
					matrix[i][j]=0;
				}
			}
		}
    }
//两个变量，但是需要记录首行首列，最后更新首行首列
	public void setZeroes1(int[][] matrix) {
		int m = matrix.length, n = matrix[0].length;
		boolean flagCol0 = false, flagRow0 = false;
		for (int i = 0; i < m; i++) {
			if (matrix[i][0] == 0) {
				flagCol0 = true;
			}
		}
		for (int j = 0; j < n; j++) {
			if (matrix[0][j] == 0) {
				flagRow0 = true;
			}
		}
		for (int i = 1; i < m; i++) {
			for (int j = 1; j < n; j++) {
				if (matrix[i][j] == 0) {
					matrix[i][0] = matrix[0][j] = 0;
				}
			}
		}
		for (int i = 1; i < m; i++) {
			for (int j = 1; j < n; j++) {
				if (matrix[i][0] == 0 || matrix[0][j] == 0) {
					matrix[i][j] = 0;
				}
			}
		}
		if (flagCol0) {
			for (int i = 0; i < m; i++) {
				matrix[i][0] = 0;
			}
		}
		if (flagRow0) {
			for (int j = 0; j < n; j++) {
				matrix[0][j] = 0;
			}
		}
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
